package org.leetcode.middle.leetcode39;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution
{

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    int sum =0;
    public List<List<Integer>> combinationSum(int[] candidates, int target)
    {
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates,target,0);
        return result;
    }



    public void backtracking(int[] candidates,int target,int start)
    {
        if (sum>target)
        {
            return;
        }

        if (sum==target)
        {
            result.add(new ArrayList<>(path));
            return;
        }


        for (int i = start; i < candidates.length; i++) {
            sum=sum+candidates[i];
            path.add(candidates[i]);

            // 递归调用，但是i不变，表示我们可以重复选择当前数字
            backtracking(candidates,target,i);

            // 回溯，撤销选择
            sum=sum-candidates[i];
            path.removeLast();

        }


    }
}
